package com.goudan.practice.array;

import java.util.Arrays;

/**
 * 三个数的最大乘积
 * 描述：给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
 */
public class MaxMultiplication {
    public static void main(String[] args) {
        int[] nums = {5, -3, 6, 8};
        System.out.println(maximumProduct(nums));
        System.out.println(maximumProduct2(nums));
    }

    /**
     * 方法一：排序
     * * 1.如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。
     * * 2.如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
     * * 3.综上，我们在给数组排序后，分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案。
     */
    public static int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
    }

    /**
     * 1.对数组进行排序;
     * 2.无论数组里面的元素的正负,最大值一定在三种情况里出现;
     * 3.分别计算三种情况下的值,取最大的即可;
     */
    public static int maximumProduct2(int[] nums) {
        Arrays.sort(nums);
        int N = nums.length;
        int res = Integer.MIN_VALUE;
        int pre = nums[0] * nums[1] * nums[2];
        int aft = nums[N - 1] * nums[N - 2] * nums[N - 3];
        int mid = nums[0] * nums[1] * nums[N - 1];
        res = Math.max(res, pre);
        res = Math.max(res, aft);
        res = Math.max(res, mid);
        return res;
    }

}
